package com.cg.offer;

import com.cg.leetcode.ListNode;
import org.junit.Test;

import java.util.Stack;

/**
 * 剑指Offer 24.反转链表
 *
 * @program: LeetCode->Offer_24
 * @description: 剑指Offer 24.反转链表
 * @author: cg
 * @create: 2022-03-10 15:22
 **/
public class Offer_24 {

    @Test
    public void test24() {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        System.out.println(reverseList(head));
    }

    /**
     * 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
     * <p>
     * 示例:
     * 输入: 1->2->3->4->5->NULL
     * 输出: 5->4->3->2->1->NULL
     * <p>
     * 限制：
     * 0 <= 节点个数 <= 5000
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            // 暂存后继节点 cur.next
            ListNode next = curr.next;
            // 修改 next 引用指向
            curr.next = prev;
            // pre 暂存 cur
            prev = curr;
            // cur 访问下一节点
            curr = next;
        }
        return prev;
        //if (head == null) {
        //    return null;
        //}
        //Stack<ListNode> stack = new Stack<>();
        //ListNode temp = head;
        //while (temp != null) {
        //    stack.push(temp);
        //    temp = temp.next;
        //}
        //head = stack.pop();
        //temp = head;
        //while (!stack.isEmpty()) {
        //    temp.next = stack.pop();
        //    temp = temp.next;
        //}
        //temp.next = null;
        //return head;
    }
}
